package top.carrotguo.search;

/**
 * fibonacci查找算法|斐波那契查找算法
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 16:00 2018-05-20
 */
public class FibSearch {

    private static int[] fib;

    /**
     * 生成fibonacci序列
     * @param size    fibonacci的长度
     */
    private static void initFib(int size){
        fib = new int[size];
        fib[0] = 0;
        fib[1] = 1;
        for (int i=2; i<size; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
    }

    /**
     *
     * @param data 有序序列
     * @param e    查找元素
     * @return     min
     */
    private int finSearch(int[] data,int e){
        int lo = 0;             //第一位
        int hi = data.length;   //最后一个元素的后一位
        int[] copyData = new int[100];
        //为后面补充有序序列做准备
        for (int i=0; i<hi;i++) {
            copyData[i] = data[i];
        }
        int k=0;
        //初始化fibonacci序列
        initFib(100);
        //找到最接近n=hi-lo的fib(k)-1那一项  并且不能比n小
        while (hi-lo>fib[k]-1) {
            k++;
        }

        //补齐有序序列(达到n=fib(k)-1的效果)
        for (int i=hi; i<fib[k]-1; i++) {
            copyData[i] = data[hi-1];
        }

        int min;
        while (lo<hi) {
            min = fib[k-1]-1;
            if (e == copyData[min]) {
                if (min<hi) {       //不是补充序列的位置
                    return min;
                } else {            //补充序列的位置 返回原始序列最后一位
                    return hi-1;
                }
            }

            if (e < copyData[min]) {
                k = k-1;
                hi = min;
            }

            if (copyData[min] < e) {
                k = k-2;
                lo = min+1;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        int[] data = {1,2,3,4,5,6,7,9};
        FibSearch fibSearch = new FibSearch();
        System.out.print(fibSearch.finSearch(data,5));
    }
}
